package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class PrintByZhi {

	public static void main(String[] args) {
		int[] pre = {3, 9, 16, 20, 15, 7};
		int[] in = {16, 9, 3, 15, 20, 7};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		PrintByZhi object = new PrintByZhi();
		System.out.println(object.printFromTopToBottom(root));
	}
	
	public List<List<Integer>> printFromTopToBottom(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		
		if (root == null) {
			return res;
		}
		List<Integer> list = new ArrayList<>();
		Stack<TreeNode> a1 = new Stack<TreeNode>(); // 用来存储偶数层的结点
		Stack<TreeNode> a2 = new Stack<TreeNode>(); // 用来存储奇数层的结点
		
		int current = 0; // 为0表示偶数层
		int next = 1; // 为1表示奇数层
		if (current == 0) {
			a1.add(root);
		} else {
			a2.add(root);
		}
		TreeNode node = null;
		// 要想之字型从上往下打印二叉树，需要两个栈，若是在奇数层，则先保存左结点的孩子的值
		// 若是偶数层，先保存右节点孩子的值，将孩子放入队列中
		// 如果队列不空，就继续扫描左右结点
		while (!a1.isEmpty() || !a2.isEmpty()) {
			// 将第一个元素出队
			if (current == 0) {
				node = a1.pop();
				list.add(node.val);
				// 用另一个栈来存储下一层的结点
				if (node.left != null) {
					a2.add(node.left);
				}
				if (node.right != null) {
					a2.add(node.right);
				}
			} else {
				node = a2.pop();
				list.add(node.val);
				if (node.right != null) {
					a1.add(node.right);
				}
				if (node.left != null) {
					a1.add(node.left);
				}
			}
			if ((current == 0 && a1.isEmpty())
					|| (current == 1 && a2.isEmpty())) {
				res.add(new ArrayList<>(list));
				list.clear();
				current = 1 - current;
				next = 1 - next;
			}
		}
		return res;
	}
}
